A. The Fair Nut and Elevator(水题)
题意
一个楼里有一个电梯,第i层有A[i]人,每个人每天用两次电梯,下楼一次和上楼一次,现在规定电梯初始处于一个点 每次有人需要电梯 ,电梯就上去到这个人的楼 载到一楼再到初始的层数
题解
发现 如果电梯在一楼和在任意一楼的接送花费是一样的,但是如果在一楼, 一楼的人需要电梯就不需要电梯额外跑两次,所以电梯在一楼最优(当然数据很小,你也可以暴力
1 | int n; |
B.Kvass and the Fair Nut (二分)
题意
N个桶,需要K升酒,问取完K升酒后 桶中剩余酒的最小值的最大是多少
题解
直接二分答案,判断把酒取到这个值能否到达K升,注意如果本身就有酒比答案小的话直接返回false
1 |
|
C.The Fair Nut and String (组合数学/DP)
题意
给你一个字符串,让你构造下标组成的严格递增序列
要求:1.这些下标对应字符串必须是‘a’
2.相邻两个下标之间必须在原字符串中隔着一个’b’
题解
把字符串分块,对于每个块中的a有块的大小种取法,但是也可以不取,所以对大小+1表示这个块都不取,然后根据乘法原理,相乘,最后因为题目要求不能有空的序列,所以答案-1;
1 | string s; |
D.The Fair Nut and the Best Path (裸的树DP 维护最大次大值)
题意
每个点都有正权值,每条边都有负权值,选择一个边,使得经过的总权值最大
题解
对于每一个点,都有走一条边和走两条边两种选择,走一条边肯定是选择权值最大的,两条边就是权值第二大的加起来;
1 |
|
E.The Fair Nut and Strings (01字典树)
题意
他写了K个字符串 ,字符串由a,b组成,c是这K个字符串的(不同前缀)的数目
他忘记了他的K个字符串,但是他还记得 这K个字符串的字典序最大T和字典序最小S 意思就是 这K个字符串最大的字符串是T最小的字符串是S
求构造K个字符串,求出这K个字符串的最大不同前缀数目;
题解
把a和b堪称0和1,然后组成一个0 1 字典树,
1.发现树的结点数就是答案;
2.k代表最多分出K个分支,
字符串T和S之间的间隔就是K个分支可以插的地方,
一个优化:如果第n层的分支数大于等于K那么肯定接下来的n+1层的结点数肯定可以有K个
1 |
|